<!DOCTYPE html>
<html dir="ltr" class="client-js" lang="de"><head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<title>Ants on Fire - Hilfe</title>
<meta charset="UTF-8">
<meta name="generator" content="MediaWiki 1.21wmf2">
<meta name="robots" content="noindex,nofollow">
<link rel="stylesheet" href="help-Dateien/load_002.css">
</style><meta name="ResourceLoaderDynamicStyles" content="">
<link rel="stylesheet" href="help-Dateien/load.css">


<body style="position: static;" class="mediawiki ltr sitedir-ltr capitalize-all-nouns ns-2 ns-subject page-Benutzer_TheZeusMan_TSP_ACO skin-vector action-submit vector-animateLayout">

		
		<!-- content -->
	
			<!-- /sitenotice -->
						<!-- firstHeading -->
			<h1 id="firstHeading" class="firstHeading"><span dir="auto">Ants on Fire - Hilfe</span></h1>
			<!-- /firstHeading -->
			<!-- bodyContent -->
			<div id="bodyContent">
								<!-- subtitle -->
				<div id="contentSub"></div>
				<!-- /subtitle -->
																<!-- jumpto -->
				
				<!-- /jumpto -->
								<!-- bodycontent -->
				<div id="mw-content-text"><div id="editnotice-ns-2"></div>
<div id="mw-edit-longpage-hint">
</div>
<div dir="ltr" class="mw-content-ltr" lang="de"><table id="toc" class="toc">
<tbody><tr>
<td>
<div id="toctitle">
<h2>Inhaltsverzeichnis</h2>
<ul>
<li class="toclevel-1 tocsection-1"><a href="#Einleitung"><span class="tocnumber">1</span> <span class="toctext">Einleitung</span></a>
<ul>
<li class="toclevel-2 tocsection-2"><a href="#Traveling_Salesman_Problem"><span class="tocnumber">1.1</span> <span class="toctext">Traveling Salesman Problem</span></a></li>
<li class="toclevel-2 tocsection-3"><a href="#Ant_Colony_Optimization"><span class="tocnumber">1.2</span> <span class="toctext">Ant Colony Optimization</span></a></li>
</ul>
</li>
<li class="toclevel-1 tocsection-4"><a href="#Das_Programm_im_Einzelnen"><span class="tocnumber">2</span> <span class="toctext">Das Programm im Einzelnen</span></a>
<ul>
<li class="toclevel-2 tocsection-5"><a href="#Genereller_Aufbau"><span class="tocnumber">2.1</span> <span class="toctext">Genereller Aufbau</span></a></li>
<li class="toclevel-2 tocsection-6"><a href="#Die_Zeichenfl.C3.A4che"><span class="tocnumber">2.2</span> <span class="toctext">Die Zeichenfläche</span></a></li>
<li class="toclevel-2 tocsection-7"><a href="#Der_Parameterbereich"><span class="tocnumber">2.3</span> <span class="toctext">Der Parameterbereich</span></a></li>
<li class="toclevel-2 tocsection-8"><a href="#Der_Iterationsmodusbereich"><span class="tocnumber">2.4</span> <span class="toctext">Der Iterationsmodusbereich</span></a></li>
<li class="toclevel-2 tocsection-9"><a href="#Ausgabebereich"><span class="tocnumber">2.5</span> <span class="toctext">Ausgabebereich</span></a></li>
<li class="toclevel-2 tocsection-10"><a href="#Die_Men.C3.BCleiste"><span class="tocnumber">2.6</span> <span class="toctext">Die Menüleiste</span></a></li>
</ul>
</li>
<li class="toclevel-1 tocsection-11"><a href="#Abschluss:"><span class="tocnumber">3</span> <span class="toctext">Abschluss:</span></a>
<ul>
<li class="toclevel-2 tocsection-12"><a href="#Format_der_.tsp_Datei"><span class="tocnumber">3.1</span> <span class="toctext">Format der .tsp Datei</span></a></li>
<li class="toclevel-2 tocsection-13"><a href="#Format_der_.opt.tour_Datei"><span class="tocnumber">3.2</span> <span class="toctext">Format der .opt.tour Datei</span></a></li>
<li class="toclevel-2 tocsection-14"><a href="#Format_der_.tspconfig_Datei"><span class="tocnumber">3.3</span> <span class="toctext">Format der .tspconfig Datei</span></a></li>
<li class="toclevel-2 tocsection-15"><a href="#Danke_und_weitere_Informationen"><span class="tocnumber">3.4</span> <span class="toctext">Danke und weitere Informationen</span></a></li>
</ul>
</li>
</ul>
</td>
</tr>
</tbody></table>
<h2> <span class="mw-headline" id="Einleitung">Einleitung</span></h2>
<p>Die Anwendung "Ants on Fire" bietet einen ACO Algorithmus um TSPs zu lösen.</p>
<h3> <span class="mw-headline" id="Traveling_Salesman_Problem">Traveling Salesman Problem</span></h3>
<p>Das Traveling Salesman Problem (TSP) beschreibt das Problem des
Handelsreisenden. Dabei soll eine Menge an Orten abgegangen werden, wobei jeder
Ort bis auf den Startort genau einmal besucht wird. Der Startort wird genau
zwei mal besucht, da er sowohl Start- als auch Zielpunkt der Reise ist.</p>
<h3> <span class="mw-headline" id="Ant_Colony_Optimization">Ant Colony Optimization</span></h3>
<p>Die Ant Colony Optimization (ACO) beschreibt die Lösung von Problemen wie
das TSP mithilfe einer Modellierung einer Ameisenkolonie. Dabei werden auf
Wegen, die eine gute Lösung versprechen, Pheromone gelegt. Anhand der
Pheromonmenge wird entschieden, ob die nächste Ameise auch diesen Weg nehmen
soll. Somit verblassen schlechte Lösungen mit wenig Pheromon, wohin gegen gute
Lösungen mit viel Pheromon bevorzugt werden.</p>
<h2> <span class="mw-headline" id="Das_Programm_im_Einzelnen">Das Programm im Einzelnen</span></h2>
<h3> <span class="mw-headline" id="Genereller_Aufbau">Genereller Aufbau</span></h3>
<p></p>
<a class="image"><img alt="general.jpg" src="help-Dateien/general.jpg" width="778" height="500" /></a>
<p></p>
<p>Die Anwendung ist in mehrere Bereiche geteilt. Der größte Bereich ist die
Zeichenfläche (1). Hier werden alle Knoten und gefundenen Touren visuell
dargestellt. Der Parameterbereich (2) dient zur Konfiguration des
ACO-Algorithmus. Im Iterationsmodusbereich (3) lassen sich der Iterationsmodus
und die Abbruchbedingung einstellen. Außerdem kann der Algorithmus hier
gestartet und gestoppt werden. Der Ausgabebereich (4) zeigt die Länge
verschiedener gefundener Touren, die vergangene Zeit und den Fortschritt. Die
Menüleiste (5) stellt eine Vielzahl an Aktionen bereit um Probleme zu laden,
speichern und andere Operationen durchzuführen. Die Bereiche 1, 2, 3 und 4 sind
in jeweils einem Tab zusammengefasst. Es können also mehrere TSPs auf einmal
bearbeitet werden.</p>
<h3> <span class="mw-headline" id="Die_Zeichenfl.C3.A4che">Die Zeichenfläche</span></h3>
<p>Die Zeichenfläche stellt die Knoten des momentan geladenen TSP und gefundene
Touren grafisch dar. Der Anwender kann durch einen Klick auf einen Knoten
diesen Auswählen. Ausgewählte Knoten können durch das Ziehen mit der Maus an
eine beliebige Stelle verschoben werden. Außerdem kann durch einen Druck auf
die Entfernentaste ein Ausgewählter Knoten entfernt werden. Durch Doppelklick
auf die Zeichenfläche wird außerdem ein Dialog geöffnet, mit dem ein neuer
Knoten hinzugefügt werden kann. Ferner kann mit dem Balken auf der rechten Seite
hinein und herausgezoomt werden.</p>
<h3> <span class="mw-headline" id="Der_Parameterbereich">Der Parameterbereich</span></h3>
<p>Der Parameterbereich dient zur Konfiguration des ACO-Algorithmus. Die Einstellbaren Parameter sind:</p>
<ul>
<li>Anzahl der Ameisen: dieser Parameter bestimmt, wie viele Ameisen pro
 Iteration die Knoten ablaufen um einen Weg zu finden. Erlaubte Werte 
sind ganze Zahlen, die größer als 0 sind.</li>
<li>Pheromonparameter: dieser Parameter bestimmt, wie wichtig das 
Pheromon auf einer Kante (die Strecke zwischen 2 Knoten) bei der Auswahl
 des Weges ist. Je größer die Zahl, desto wichtiger der Pheromonwert der
 Kante. Erlaubte Werte sind Dezimalzahlen zwischen 0 (exklusive) und 5 
(inklusive).</li>
<li>Lokale Information: dieser Parameter bestimmt, wie wichtig die 
Entfernung zwischen 2 Knoten bei der Auswahl des Weges ist. Je größer 
der Wert, desto mehr werden kürzere Distanzen bevorzugt. Erlaubte Werte 
sind Dezimalzahlen zwischen 0 (exklusive) und 5 (inklusive).</li>
<li>Verdunstungsparameter: dieser Parameter bestimmt, wie viel Pheromon 
auf allen Kanten nach einer Iteration verdunstet. Bei einem 
Verdunstungsparameterwert von 0,25 verdunsten 25% der Pheromone auf 
allen Kanten nach einer Iteration. Erlaubte Werte sind Dezimalzahlen 
zwischen 0 (exklusive) und 1 (inklusive).</li>
<li>Initialer Pheromonwert: dieser Parameter bestimmt, wie viel Pheromon
 beim Algorithmusstart bereits auf den Kanten liegt. Erlaubte Werte sind
 Dezimalzahlen größer als 0.</li>
<li>Pheromonupdateparameter: dieser Parameter bestimmt, wie viel 
Pheromon eine Ameise auf dieser Kante hinterlässt, wenn sie darüber 
gelaufen ist. Größere Werte bedeuten dabei ein Hinterlassen größerer 
Pheromonmengen. Erlaubte Werte sind Dezimalzahlen größer als 0.</li>
</ul>
<h3> <span class="mw-headline" id="Der_Iterationsmodusbereich">Der Iterationsmodusbereich</span></h3>
<p>In diesem Bereich kann der Iterarionsmodus und die Abbruchbedingung 
eingestellt werden. Die Iterationsmodi, die zur Auswahl stehen, sind:</p>
<ul>
<li>Iterationsanzahl: es wird eine bestimmte Anzahl oft iteriert, diese 
Anzahl lässt sich im Textfeld hinter dem Optionsfeld einstellen. 
Erlaubte Werte sind ganze Zahlen größer als 0.</li>
<li>Tourlänge: es wird solange iteriert, bis eine Strecke gefunden 
wurde, deren Länge kürzer als oder gleich der eingestellten Länge ist. 
Erlaubte Werte sind Dezimalzahlen größer als 0.</li>
<li>Optimale Tour: es wird solange iteriert, bis eine eingestellte 
Lösung gefunden wurde. Mit dem Button hinter dem Optionsfeld kann eine 
.opt.tour Datei geladen werden. Diese Datei muss einer bestimmten Norm 
entspechen, wie in Abschnitt 3 erläutert. Es wird solange iteriert, bis 
eine Ameise exakt eine Folge von Knoten abgelaufen ist.</li>
</ul>
<p>Mit dem linken Button lässt sich der Algorithmus starten und stoppen.
 Der Algorithmus kann nur gestartet werden, wenn mindestens zwei Knoten 
existieren und alle eingegebenen Parameter der Norm entsprechen. Sind 
diese Bedingungen nicht gegeben, wird der Button ausgegraut. Mit dem 
rechten Button kann der Algorithmus pausiert und wieder aufgenommen werden. 
Diese Option ist nur verfügbar, falls der Algorithmus vorher gestartet 
wurde.</p>
<h3> <span class="mw-headline" id="Ausgabebereich">Ausgabebereich</span></h3>
<p>Hier werden die errechneten Tourlängen, die vergangene Zeit und ein 
Fortschrittsbalken angezeigt. Der "Beste Tour"-Bereich zeigt zwei Werte 
an:</p>
<ul>
<li>Iteration: das ist die kürzeste Strecke, die eine Ameise in der letzten Iteration gefunden hat.</li>
<li>Global: das ist die kürzeste Strecke, die eine Ameise seit dem Start des Algorithmus gefunden hat.</li>
</ul>
<p>Der "Durchschnittliche Tour"-Bereich zeigt ebenfalls zwei Werte an:</p>
<ul>
<li>Iterationen: das ist die durchschnittliche Länge aller Strecken, die alle Ameisen in der letzten Iteration gelaufen sind.</li>
<li>Global: das ist die durchschnittliche Länge aller Strecken, die alle Ameisen seit dem Start des Algorithmus gelaufen sind.</li>
</ul>
<p>Das "Verstrichene Zeit"-Feld zeigt die Zeit in Millisekunden an, die 
seit dem Start des Algorithmus vergangen sind. Der Fortschrittsbalken 
funktioniert je nach eingestellten Iterationsmodus anders. Wenn der 
Iterationsmodus "Iterationsanzahl" ist, wächst der Fortschrittbalken mit
 jeder fertiggestellten Iteration, wobei das Maximum die eingestellte 
Iterationsanzahl ist. Ist der Iterationsmodus "Tourlänge" oder "Optimale
 Tour", so verbleibt der Fortschrittsbalken bei 50%, da bei diesen 
beiden Iterationsmodi nicht bekannt ist, wann der Algorithmus 
terminiert. So dient er nur zur Anzeige, dass eine Aktion stattfindet.</p>
<h3> <span class="mw-headline" id="Die_Men.C3.BCleiste">Die Menüleiste</span></h3>
<p>Die Menüleiste hat drei Kategorien: Datei, Bearbeiten und Hilfe. Das Dateimenü:</p>
<ul>
<li>Neuer Tab: hiermit lässt sich ein neuer Tab erstellen. Nahezu alle 
Menüpunkte beziehen sich auf den momentan ausgewählten Tab. Jeder Tab 
arbeitet jedoch völlig unabhängig von den anderen Tabs, somit können 
mehrere Projekte gleichzeitig geöffnet sein.</li>
<li>TSP Datei öffnen: dieser Menüpunkt öffnet einen Dialog, mit dem sich
 eine .tsp Datei öffnen lässt. Die geöffnete Datei wird in den momentan 
aktiven Tab geladen und überschreibt das zuvor geladene TSP. Die 
geöffnete Datei muss bestimmten Normen entsprechen, die im dritten 
Abschnitt erläutert werden.</li>
<li>TSP Datei speichern: speichert das TSP des momentan aktiven Tabs. 
Wurde zuvor kein TSP geöffnet und diese Option zum ersten Mal gewählt, 
öffnet sich ein Dialog zur Auswahl des Speicherortes. Jede weitere 
Aktivierung dieses Menüpunktes speichert automatisch an den zuvor 
gewählten Speicherplatz.</li>
<li>TSP Datei speichern unter...: funktioniert genau wie TSP Datei 
speichern, mit dem Unterschied, dass sich der Dialog zur Auswahl des 
Speicherortes immer öffnet.</li>
<li>Konfigurationsdatei öffnen: dieser Menüpunkt öffnet einen Dialog, 
mit dem sich eine .tspconfig Datei öffnen lässt. Die geöffnete Datei 
wird in den momentan aktiven Tab geladen und überschreibt die 
bestehenden Werte des Parameterbereiches. Die geöffnete Datei muss 
bestimmten Normen entsprechen, die im dritten Abschnitt erläutert 
werden.</li>
<li>Konfigurationsdatei speichern: speichert die Werte des 
Parameterbereiches des momentan aktiven Tabs. Wurde zuvor keine 
Konfigurationsdatei geöffnet und diese Option zum ersten Mal gewählt, 
öffnet sich ein Dialog zur Auswahl des Speicherortes. Jede weitere 
Aktivierung dieses Menüpunktes speichert automatisch an den zuvor 
gewählten Speicherplatz.</li>
<li>Konfigurationsdatei speichern unter...:funktioniert genau wie 
Konfigurationsdatei speichern, mit dem Unterschied, dass sich der Dialog
 zur Auswahl des Speicherortes immer öffnet.</li>
<li>Beenden: beendet die Anwendung.</li>
</ul>
<p>Das Bearbeitenmenü:</p>
<ul>
<li>Zufallsprojekt erstellen: öffnet einen Dialog, um ein Zufallsprojekt
 zu erstellen. Es kann spezifiziert werden, wie viele Knoten erzeugt 
werden sollen (ganze Zahlen größer/gleich 0). Ist dieser Wert 0, wird 
eine zufällige Anzahl an Knoten erstellt. Die anderen beiden Werte 
bestimmten den Koordinatenbereich, in dem sich die erstellten Knoten 
befinden (Dezimalzahlen größer/gleich 0). Sind diese Werte 0, wird ein 
zufälliger Bereich gwählt. Ein Klick auf Erstellen erstellt dieses 
Projekt und lädt es in den momentan aktiven Tab, wobei das zuvor 
geladene TSP überschrieben wird. Ein Klick auf Abbrechen schließt den 
Dialog ohne etwas zu erstellen.</li>
<p></p>
<a class="image"><img alt="randomprojectdialog.jpg" src="help-Dateien/randomprojectdialog.jpg" width="259" height="151" /></a>
<p></p>
<li>Zufallsparameter erstellen: generiert zufällige Werte in den 
Parameterbereich des momentan aktiven Tabs, wobei die bestehenden Werte 
überschrieben werden.</li>
<li>TSP Daten bearbeiten: öffnet einen Dialog, mit dem sich die TSP 
Daten des momentan aktiven Tabs bearbeiten lassen. Zu diesen Daten 
gehören momentan nur der Name und das Kommentar, alle anderen Werte sind
 festgesetzt. Ein Klick auf Speichern speichert die eingegebenen Werte. 
Ein Klick auf Abbrechen schließt den Dialog ohne etwas zu speichern.</li>
<li>Eigenschaften: öffnet einen Dialog, mit dem sich die Eigenschaften 
bearbeiten lassen. Eigenschaften gelten global und sind somit für jeden 
Tab gleich.</li>
</ul>
<dl>
<dd>
<ul>
<li>Antialiasing: bestimmt, ob beim Zeichnen auf der Zeichenfläche 
Antialiasing verwendet werden soll. Antialising sieht schöner aus, 
braucht aber mehr Rechenleistung. Bei sehr großen TSP oder langsamen 
Computern sollte diese Option aus sein.</li>
<li>Neuzeichnungsintervall: bestimmt, nach wie vielen Iterationen die 
Knoten und Kanten auf der Zeichenfläche neu gezeichnet werden sollen. 
Bei großen TSP und langsamen Computern sollte dieser Wert erhöht werden,
 da das Zeichnen relativ anspruchsvoll ist. Erlaubte Werte sind ganze 
Zahlen größer als 0.</li>
<li>Alle weiteren Punkte dienen zur Auswahl der Farbe, mit der die 
Knoten und Strecken auf der Zeichenfläche gezeichnet werden sollen. Ein 
Klick auf die Farbrechtecke öffnet einen weiteren Dialog, mit dem eine 
andere Farbe ausgewählt werden kann.</li>
<p></p>
<a class="image"><img alt="propertydialog.jpg" src="help-Dateien/propertydialog.jpg" width="291" height="242" /></a>
</ul>
</dd>
</dl>
<p>Ein Klick auf speichern speichert die Einstellungen. Ein Klick auf Abbrechen verwirft geänderte Einstellungen.</p>
<p>Das Hilfemenü:</p>
<ul>
<li>Hilfe: öffnet die Hilfeseite, die Sie sich gerade ansehen.</li>
<li>Über: öffnet einen Dialog, der Informationen über die Entwickler dieser Anwendung anzeigt.</li>
</ul>
<h2> <span class="mw-headline" id="Abschluss:">Abschluss:</span></h2>
<h3> <span class="mw-headline" id="Format_der_.tsp_Datei">Format der .tsp Datei</span></h3>
<a class="image"><img alt="tspfile.jpg" src="help-Dateien/tspfile.jpg" width="206" height="251" /></a>
<p>Bis auf die Werte NAME, COMMENT und DIMENSION müssen alle Werte den 
Werten auf dem Bild entsprechen. NAME und COMMENT können frei gewählt 
werden, DIMENSION entspricht der Anzahl der Einträge nach 
NODE_COORD_SECTION. Ein Knoteneintrag hat folgendes Format: 
KNOTENNUMMER&lt;Leerzeichen&gt;X_KOORDINATE&lt;Leerzeichen&gt;Y_KOORDINATE.
 Nach dieser Auflistung folgt noch ein EOF.</p>
<h3> <span class="mw-headline" id="Format_der_.opt.tour_Datei">Format der .opt.tour Datei</span></h3>
<a class="image"><img alt="opttourfile.jpg" src="help-Dateien/opttourfile.jpg" width="182" height="235" /></a>
<p>NAME muss dem Namen des TSP des momentan aktiven Tabs mit dem Anhang 
".opt.tour" entsprechen. TYPE ist immer TOUR. DIMENSION entspricht der 
Anzahl der Knoten. Nach TOUR_SECTION wird dann die Reihenfolge der 
Knoten angegeben. Pro Zeile ist dabei nur eine Zahl vorhanden. Diese 
Zahl gibt den Index des Knotens in der .tsp Datei an. Als letzte Zahl 
folgt eine -1, danach ein EOF.</p>
<h3> <span class="mw-headline" id="Format_der_.tspconfig_Datei">Format der .tspconfig Datei</span></h3>
<p>Diese Datei wird von der Anwendung erstellt und verwendet, sie sollte
 nicht außerhalb erstellt werden. Deswegen wird der Inhalt hier nicht 
erläutert.</p>
<h3> <span class="mw-headline" id="Danke_und_weitere_Informationen">Dank</span></h3>
<p>an famfamfam.com für die verwendeten Silk Icons</p>
</body></html>